package com.ken.algorithms.linkedList;

/**
 * <ul>
 * <li>Title: DLinkedList</li>
 * <li>Description: 双向链表 </li>
 * </ul>
 *
 * @author 程序员ken
 * @date 2021/5/20 22:16
 */
public class DLinkedList<E> {

    private int size = 0;

    transient Node<E> first;

    transient Node<E> last;


   public boolean add(E e) {
      linkLast(e);
      return true;
    }


    /**
     * Links e as last element.(向后添加元素)
     */
    void linkLast(E e) {
        final Node<E> ln = last;// 记录用于是上一次节点（新增节点）
        final Node<E> nowNode =new Node<E>(last,e,null);
        last = nowNode;
        if(ln==null){
            first =nowNode;
        }
        else{
            ln.next = nowNode;
        }
        size++;
    }

    /**
     * Links e as first element.(向前添加元素)
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<E>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
    }

    //删除元素  双链表需要操作前后节点 单链表只需要操作后置节点
    public boolean remove(int index){
        if(size<=0 || size < index+1){
            return false;
        }
        else{
            Node<E> ln = index==0?first: (index==size-1)?last:null; //首尾取值优选
            Node<E> next = null;
            Node<E> prev = null;
            if(ln!=null){
                setLinkedValue(ln);
            }

            int count =0;
            while (ln.next!=null){
                ln = ln.next;
                count++;
                if(count==index){
                    setLinkedValue(ln);
                    break;
                }
            }

            return true;
        }
    }

    /**
     * 功能描述: 设置双链表的值
     * @param ln
     * @return: void 
     * @author: 程序员ken
     * @date: 2021/5/21 0021 下午 12:50
    */ 
    private void setLinkedValue(Node<E> ln) {
        Node<E> prev;
        Node<E> next;
        prev  = ln.prev;// 当前节点前置节点
        next = ln.next;// 当前节点后置节点
        if(prev!=null){// 说明是非首节点
            ln.prev.next = next;// 前置节点的后置节点 等于当前点击的后置节点
        }else{ //说明是首节点
            this.first = first.next;
        }
        if(next!=null){
            ln.next.prev = prev;// 前置节点的后置节点 等于当前点击的后置节点
        }else{// 说明是尾结点
            this.last = this.size<=1?this.first:prev;//后置没有了 说明要么全部删了 要么只剩一个节点
        }
        this.size--;
    }


    //取出元素
    public E get(int index){
        if (index >= size){
            throw new IndexOutOfBoundsException(String.format("Index:%s, Size:%s",index,this.size));
        }
        else{
            //首尾取值优选
            if(index==0 || index== this.size-1){
                return index == this.size-1?this.last.item:this.first.item;
            }
            Node<E> ln = first;
            int count =0;
            while (ln.next!=null){
                ln = ln.next;
                count++;
                if(count==index){
                    break;
                }
            }
            return ln.item;
        }
    }

    public int size(){
        return this.size;
    }

    static class Node<E>{
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }

    }


    public static void main(String[] args) {
        DLinkedList<Integer> myLinkedList = new DLinkedList<Integer>();
        myLinkedList.add(1);
        myLinkedList.add(16);
        myLinkedList.add(99);
        myLinkedList.add(75);
        myLinkedList.add(65);
        myLinkedList.remove(0);

        for (int i = 0; i < myLinkedList.size(); i++) {
            System.out.println(myLinkedList.get(i));
        }



        System.out.println("");
        //System.out.println(myLinkedList.get(0));

    }



}
